package com.demo.study.algorithm.sorts;

import com.demo.study.utils.ArrayUtil;

import static com.demo.study.utils.ArrayUtil.printArray;

/**
 * 插入排序
 *
 * @author Baymax
 * @since 2024-08-07
 */
public class B04_InsertionSort {
    public static void main(String[] args) {
        int[] nums = ArrayUtil.intRandomArray();
        printArray(nums);
        insertionSort(nums);
        printArray(nums);

        System.out.println("-----------------");

        nums = ArrayUtil.intRandomArray();
        printArray(nums);
        insertionSortIf(nums);
        printArray(nums);

        System.out.println("-----------------");

        int[] nums2 = ArrayUtil.intRandomArray();
        printArray(nums2);
        insertionSortRecursion(nums2);
        printArray(nums2);
    }

    /**
     * 插入排序：在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置
     * 从大到小进行比较，如果已排序的最右侧 > 基准元素，则已排序的右移一位
     * 时间复杂度：O(n^2)
     */
    public static void insertionSort(int[] nums) {
        // 外循环：已排序区间为 [0, i-1]
        for (int i = 1; i < nums.length; i++) {
            int base = nums[i]; // 当前的基准元素
            int j = i - 1; // 已排元素最右侧开始比较
            // 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
            while (j >= 0 && nums[j] > base) {
                nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
                j--;
            }
            if (j != i - 1) {
                nums[j + 1] = base; // 将 base 赋值到正确位置
            }
        }
    }

    /**
     * 插入排序-for循环实现方式
     */
    public static void insertionSortIf(int[] nums) {
        // 外循环：以第一个元素为基准，后续元素逐个插入
        for (int i = 1; i < nums.length; i++) {
            int base = nums[i]; // 当前的基准元素
            // 在已排序的集合中，找到正确位置，比当前元素大的，进行后移
            int j = i - 1; // 已排序的元素个数
            for (; j >= 0; j--) {
                if (nums[j] > base) {
                    nums[j + 1] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + 1] = base;
        }
    }

    /**
     * 插入排序-递归实现
     */
    public static void insertionSortRecursion(int[] nums) {
        doInsertionSortRecursion(nums, 1);
    }

    /**
     * @param nums 待排序集合
     * @param low 未排序左边界索引
     */
    private static void doInsertionSortRecursion(int[] nums, int low) {
        if (low == nums.length) {
            return;
        }
        int base = nums[low]; // 待插入的元素
        int i = low - 1; // 已排序最右侧元素

        // 查询比base小的第一个元素位置
        while (i >= 0 && nums[i] > base) {
            nums[i + 1] = nums[i]; // 已排序的最大值右移
            i--;
        }

        nums[i + 1] = base;
        doInsertionSortRecursion(nums, low + 1);
    }

}
